package a10_动态规划;

/**
 * <p>
 * a17_一和零
 * </p>
 *
 * @author flyduck
 * @since 2025/2/12
 */
public class a17_一和零 {
    //抽象成能装m个0和n个1的一个容器(两个维度的背包，还是01背包)
    //装满这个背包最多有多少个物品

    //因为是3个变量，所以定义二维数组
    //dp[i][j]:装满i个0和j个1的背包最多能装的物品数量为dp[i][j]

    //每个物品的重量是：x个0 y个1
    //递推公式：
    //dp[i][j] = Math.max(dp[i][j],dp[i-x][j-y] + 1);

    //初始化：
    // dp[0][0] = 0

    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        dp[0][0] = 0;

        for (String str : strs) {//遍历每个物品
            int x = 0,y=0;//每个物品的重量
            for (char c : str.toCharArray()) {
                if(c == '0'){
                    x++;
                }else {
                    y++;
                }
            }

            //遍历背包重量
            for (int i = m; i >= x; i--) {
                for (int j = n; j >= y; j--) {
                    dp[i][j] = Math.max(dp[i][j],dp[i-x][j-y] + 1);
                }
            }
        }
        return dp[m][n];
    }
}
